<template>
  <div class="merge-sort">
    <h1 class="title">归并排序算法可视化</h1>

    <div class="algorithm-description">
      <h2 class="section-title">算法描述</h2>
      <div class="description-content">
        <p>归并排序是一种分治算法，通过将数组分成两半分别排序，然后将排序好的两半合并在一起。</p>
        <p><strong>算法步骤：</strong></p>
        <ol>
          <li>将数组分成两半</li>
          <li>对每一半递归地进行归并排序</li>
          <li>将两个已排序的子数组合并成一个有序数组</li>
        </ol>
        <p><strong>时间复杂度：</strong></p>
        <ul>
          <li>最坏情况：O(n log n)</li>
          <li>最好情况：O(n log n)</li>
          <li>平均情况：O(n log n)</li>
        </ul>
        <p><strong>空间复杂度：</strong> O(n) - 需要额外的空间来合并</p>
      </div>
    </div>

    <div class="control-panel">
      <el-button type="primary" @click="startSorting" :disabled="isSorting">
        <i class="el-icon-video-play"></i> {{ isSorting ? '排序中...' : '开始排序' }}
      </el-button>
      <el-button @click="pauseSorting" :disabled="!isSorting || isPaused">
        <i class="el-icon-video-pause"></i> 暂停
      </el-button>
      <el-button @click="resumeSorting" :disabled="!isPaused">
        <i class="el-icon-caret-right"></i> 继续
      </el-button>
      <el-button @click="resetArray" :disabled="isSorting && !isPaused">
        <i class="el-icon-refresh"></i> 重置
      </el-button>

      <el-slider v-model="speed" :min="100" :max="1000" :step="100" :disabled="isSorting && !isPaused"
        class="speed-slider">
        <template #prefix>
          <i class="el-icon-time"></i>
        </template>
      </el-slider>
    </div>

    <div class="visualization-container">
      <div class="array-container">
        <div v-for="(item, index) in array" :key="index" class="array-bar" :style="{
          height: item * 5 + 'px',
          backgroundColor: activeIndexes.includes(index) ? '#FF6B6B' : '#4ECDC4',
          boxShadow: activeIndexes.includes(index) ? '0 0 10px rgba(255,107,107,0.7)' : 'none'
        }">
          <span class="bar-value">{{ item }}</span>
        </div>
      </div>
    </div>

    <div class="code-section">
      <h2 class="section-title">代码实现</h2>
      <div class="code-container">
        <el-tabs type="border-card" v-model="currentLanguage">
          <el-tab-pane v-for="(_, lang) in codeLanguages" :key="lang" :label="lang" :name="lang">
            <el-button class="copy-btn" @click="copyCode" type="default" :icon="CopyDocument"></el-button>
            <pre><code>{{ codeLanguages[lang] }}</code></pre>
          </el-tab-pane>
        </el-tabs>
      </div>
    </div>
  </div>
</template>

<script setup>
import { ref } from 'vue'
import { CopyDocument } from '@element-plus/icons-vue'
import { ElMessage } from 'element-plus'

// 响应式数据
const isSorting = ref(false)
const isPaused = ref(false)
const speed = ref(500)
const sortingPromise = ref(null)
const sortingResolve = ref(null)
const array = ref([])
const activeIndexes = ref([])
const currentLanguage = ref('JavaScript')
const code = ref('')

// 代码语言定义
const codeLanguages = {
  JavaScript: `function mergeSort(arr) {
  if (arr.length <= 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

function merge(left, right) {
  let result = [];
  let i = 0, j = 0;

  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }

  return result.concat(left.slice(i)).concat(right.slice(j));
}`,
  Java: `public class MergeSort {
  public static void mergeSort(int[] arr) {
    if (arr.length <= 1) return;

    int mid = arr.length / 2;
    int[] left = Arrays.copyOfRange(arr, 0, mid);
    int[] right = Arrays.copyOfRange(arr, mid, arr.length);

    mergeSort(left);
    mergeSort(right);

    merge(arr, left, right);
  }

  private static void merge(int[] result, int[] left, int[] right) {
    int i = 0, j = 0, k = 0;

    while (i < left.length && j < right.length) {
      if (left[i] < right[j]) {
        result[k++] = left[i++];
      } else {
        result[k++] = right[j++];
      }
    }

    while (i < left.length) {
      result[k++] = left[i++];
    }

    while (j < right.length) {
      result[k++] = right[j++];
    }
  }
}`,
  Python: `def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])
    result.extend(right[j:])

    return result`,
  Golang: `func mergeSort(arr []int) []int {
    if len(arr) <= 1 {
        return arr
    }

    mid := len(arr) / 2
    left := mergeSort(arr[:mid])
    right := mergeSort(arr[mid:])

    return merge(left, right)
}

func merge(left, right []int) []int {
    result := make([]int, 0, len(left)+len(right))
    i, j := 0, 0

    for i < len(left) && j < len(right) {
        if left[i] < right[j] {
            result = append(result, left[i])
            i++
        } else {
            result = append(result, right[j])
            j++
        }
    }

    result = append(result, left[i:]...)
    result = append(result, right[j:]...)

    return result
}`,
  C: `void mergeSort(int arr[], int n) {
  if (n <= 1) return;

  int mid = n / 2;
  int* left = malloc(mid * sizeof(int));
  int* right = malloc((n - mid) * sizeof(int));

  for (int i = 0; i < mid; i++) left[i] = arr[i];
  for (int i = mid; i < n; i++) right[i - mid] = arr[i];

  mergeSort(left, mid);
  mergeSort(right, n - mid);

  merge(arr, left, mid, right, n - mid);

  free(left);
  free(right);
}

void merge(int arr[], int left[], int leftSize, int right[], int rightSize) {
  int i = 0, j = 0, k = 0;

  while (i < leftSize && j < rightSize) {
    if (left[i] < right[j]) {
      arr[k++] = left[i++];
    } else {
      arr[k++] = right[j++];
    }
  }

  while (i < leftSize) arr[k++] = left[i++];
  while (j < rightSize) arr[k++] = right[j++];
}`,
  Rust: `fn merge_sort(arr: &mut [i32]) {
  if arr.len() <= 1 {
    return;
  }

  let mid = arr.len() / 2;
  let mut left = arr[..mid].to_vec();
  let mut right = arr[mid..].to_vec();

  merge_sort(&mut left);
  merge_sort(&mut right);

  merge(arr, &left, &right);
}

fn merge(arr: &mut [i32], left: &[i32], right: &[i32]) {
  let mut i = 0;
  let mut j = 0;
  let mut k = 0;

  while i < left.len() && j < right.len() {
    if left[i] < right[j] {
      arr[k] = left[i];
      i += 1;
    } else {
      arr[k] = right[j];
      j += 1;
    }
    k += 1;
  }

  while i < left.len() {
    arr[k] = left[i];
    i += 1;
    k += 1;
  }

  while j < right.len() {
    arr[k] = right[j];
    j += 1;
    k += 1;
  }
}`
}

// 初始化数组
const resetArray = () => {
  array.value = Array.from({ length: 10 }, () => Math.floor(Math.random() * 50) + 5)
  activeIndexes.value = []
}

// 复制代码
const copyCode = async () => {
  try {
    await navigator.clipboard.writeText(code.value)
    ElMessage.success('复制成功')
  } catch (err) {
    console.error('复制失败: ', err)
    ElMessage.error('复制失败')
  }
}

// 排序控制
const startSorting = async () => {
  if (isSorting.value) {
    return
  }

  isSorting.value = true
  isPaused.value = false
  const arr = [...array.value]

  await mergeSort(arr, 0, arr.length - 1)

  activeIndexes.value = []
  isSorting.value = false
  isPaused.value = false
  sortingResolve.value = null
}

async function mergeSort(arr, left, right) {
  if (left >= right) return

  const mid = Math.floor((left + right) / 2)

  await mergeSort(arr, left, mid)
  await mergeSort(arr, mid + 1, right)

  await merge(arr, left, mid, right)
}

async function merge(arr, left, mid, right) {
  const leftArr = arr.slice(left, mid + 1)
  const rightArr = arr.slice(mid + 1, right + 1)

  let i = 0, j = 0, k = left

  while (i < leftArr.length && j < rightArr.length) {
    if (isPaused.value) {
      await new Promise(resolve => {
        sortingResolve.value = resolve
      })
    }

    activeIndexes.value = [k]
    await new Promise(resolve => {
      sortingPromise.value = setTimeout(resolve, 1100 - speed.value)
    })

    if (leftArr[i] <= rightArr[j]) {
      arr[k] = leftArr[i]
      i++
    } else {
      arr[k] = rightArr[j]
      j++
    }

    k++
    array.value = [...arr]
  }

  while (i < leftArr.length) {
    arr[k] = leftArr[i]
    i++
    k++
    array.value = [...arr]
  }

  while (j < rightArr.length) {
    arr[k] = rightArr[j]
    j++
    k++
    array.value = [...arr]
  }
}

const pauseSorting = () => {
  if (!isSorting.value) {
    return
  }
  isPaused.value = true
}

const resumeSorting = () => {
  if (!isPaused.value) {
    return
  }
  isPaused.value = false
  if (sortingResolve.value) {
    const resolve = sortingResolve.value
    sortingResolve.value = null
    resolve()
  } else {
    startSorting()
  }
}

// 初始化
resetArray()
</script>

<style scoped>
.merge-sort {
  --bg-color: #ffffff;
  --text-color: #333333;
  --primary-color: #409eff;
  --border-color: #dcdfe6;
  --code-bg: #f5f7fa;
  --bar-bg: #e4e7ed;
  --active-bar-bg: #f56c6c;
  max-width: 100%;
  min-height: 100vh;
  margin: 0;
  padding: 1rem;
  background-color: var(--bg-color);
  color: var(--text-color);
}

.title {
  text-align: center;
  color: var(--text-color);
  margin: 1rem 0;
  font-weight: 500;
  font-size: clamp(1.5rem, 4vw, 2rem);
}

.algorithm-description {
  background: var(--bg-color);
  border-radius: 4px;
  padding: 1rem;
  margin-bottom: 1.5rem;
  border: 1px solid var(--border-color);
}

.description-content {
  line-height: 1.6;
  font-size: clamp(0.9rem, 2vw, 1rem);
}

.control-panel {
  display: flex;
  flex-wrap: wrap;
  justify-content: center;
  align-items: center;
  gap: 0.8rem;
  margin-bottom: 1.5rem;
}

.speed-slider {
  width: clamp(150px, 30vw, 250px);
  margin-left: 0.5rem;
}

.visualization-container {
  background: var(--bg-color);
  border-radius: 4px;
  padding: 1rem;
  margin-bottom: 1.5rem;
  border: 1px solid var(--border-color);
}

.array-container {
  display: flex;
  justify-content: center;
  align-items: flex-end;
  height: 250px;
  gap: 0.3rem;
}

.array-bar {
  width: clamp(20px, 4vw, 40px);
  background: var(--bar-bg);
  border-radius: 2px 2px 0 0;
  transition: all 0.3s ease;
  display: flex;
  flex-direction: column;
}

.array-bar.active {
  background: var(--active-bar-bg);
  border-color: var(--active-bar-bg);
}

.code-container {
  position: relative;
  border-radius: 4px;
  overflow: hidden;
  border: 1px solid var(--border-color);
}

.bar-value {
  margin-bottom: 5px;
  font-size: clamp(0.6rem, 1.5vw, 0.8rem);
}

.copy-btn {
  position: absolute;
  right: 10px;
  top: 10px;
  z-index: 1;
}

pre {
  overflow: auto;
}

@media (max-width: 768px) {
  .insertion-sort {
    padding: 0.5rem;
  }

  .control-panel {
    gap: 0.3rem;
    flex-direction: column;
    align-items: stretch;
  }

  .array-container {
    height: 180px;
    gap: 0.2rem;
  }

  .array-bar {
    width: clamp(15px, 3vw, 25px);
  }

  .speed-slider {
    width: 100%;
    margin-left: 0;
  }

  .description-content {
    font-size: 0.8rem;
  }
}
</style>
